#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/11 8:26
# ===========================================
#       题目名称： 68. 文本左右对齐
#       题目地址： https://leetcode.cn/problems/text-justification/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    """
        给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
        你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有
    maxWidth 个字符。
        要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
        文本的最后一行应为左对齐，且单词之间不插入额外的空格。
    注意:
        单词是指由非空格字符组成的字符序列。
        每个单词的长度大于 0，小于等于 maxWidth。
        输入单词数组 words 至少包含一个单词。
    """

    def fullJustify(self, words, maxWidth):
        # 对单词进行分组
        all_line_words = []  # 所有行的单词
        line_words = []  # 每行存放的单词
        cur_line_width = 0  # 当前单词已占的宽度
        for index, word in enumerate(words):
            if len(line_words) + cur_line_width + len(word) > maxWidth:
                all_line_words.append(line_words)
                line_words = []
                cur_line_width = 0
            line_words.append(word)
            cur_line_width += len(word)
            if index == len(words) - 1:
                all_line_words.append(line_words)
        # 寻找每一行中剩余的平均行数
        for index, line_words in enumerate(all_line_words):
            if len(line_words) == 1:
                all_line_words[index][0] = all_line_words[index][0].ljust(maxWidth)
            elif index == len(all_line_words) - 1:
                # 若果是最后一行 左对齐
                cur_line_avg_width = maxWidth  # 当前行剩余的宽度
                for ind, word in enumerate(line_words):
                    cur_line_avg_width -= len(word)
                    if len(line_words) - 1 != ind:
                        cur_line_avg_width -= 1
                        all_line_words[index][ind] += " "
                    else:
                        all_line_words[index][ind] += "".ljust(cur_line_avg_width)
            else:
                cur_line_avg_width = maxWidth  # 当前行剩余的宽度
                for ind, word in enumerate(line_words):
                    cur_line_avg_width -= len(word)
                    if len(line_words) - 1 != ind:
                        cur_line_avg_width -= 1
                        all_line_words[index][ind] += " "
                while cur_line_avg_width > 0:
                    for ind, word in enumerate(line_words):
                        if ind == len(line_words) - 1:
                            break
                        all_line_words[index][ind] += " "
                        cur_line_avg_width -= 1
                        if cur_line_avg_width <= 0:
                            break
        return ["".join(line_words) for line_words in all_line_words]

    def fullJustify2(self, words, maxWidth):
        """
            @param words {list} 单词
            @param maxWidth {int} 最大宽度
            @result {list[string-case]} 返回值
            使用贪心算法完成
        """
        res, line, str_num = [], [], 0
        for word in words:
            # line中所有单词加一起的长度 + line中单词(单词与单词之间原生需要1个空格)之间的间距数 + 当前需要判断的单词长度
            # 上述之和大于等于maxWidth时会溢出，为什么等于时也会溢出？因为若新加入Word，会新增加1个间距(即空格长度)
            if str_num + len(line) - 1 + len(word) >= maxWidth:
                for i in range(maxWidth - str_num):
                    line[i % max(len(line) - 1, 1)] += ' '  # 循环将每个空格依次加到每个单词之间的间距上
                res.append(''.join(line))
                line, str_num = [], 0
            line.append(word)
            str_num += len(word)
        return res + [' '.join(line).ljust(maxWidth)]


if __name__ == '__main__':
    s = Solution()
    # [
    #    "This    is    an",
    #    "example  of text",
    #    "justification.  "
    # ]
    print(s.fullJustify(words=["This", "is", "an", "example", "of", "text", "justification."], maxWidth=16))
    # [
    #   "What   must   be",
    #   "acknowledgment  ",
    #   "shall be        "
    # ]
    print(s.fullJustify(words=["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth=16))
    #  [
    #   "Science  is  what we",
    #   "understand      well",
    #   "enough to explain to",
    #   "a  computer.  Art is",
    #   "everything  else  we",
    #   "do                  "
    # ]
    print(s.fullJustify(words=["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"], maxWidth=20))
